package binarySearch;

import java.util.HashSet;

/**
 * @author pengfei.hpf
 * @date 2020/3/30
 * @verdion 1.0.0
 * 1062. 最长重复子串
 * 给定字符串 S，找出最长重复子串的长度。如果不存在重复子串就返回 0。
 *
 *
 *
 * 示例 1：
 *
 * 输入："abcd"
 * 输出：0
 * 解释：没有重复子串。
 * 示例 2：
 *
 * 输入："abbaba"
 * 输出：2
 * 解释：最长的重复子串为 "ab" 和 "ba"，每个出现 2 次。
 * 示例 3：
 *
 * 输入："aabcaabdaab"
 * 输出：3
 * 解释：最长的重复子串为 "aab"，出现 3 次。
 * 示例 4：
 *
 * 输入："aaaaa"
 * 输出：4
 * 解释：最长的重复子串为 "aaaa"，出现 2 次。
 *
 *
 * 提示：
 *
 * 字符串 S 仅包含从 'a' 到 'z' 的小写英文字母。
 * 1 <= S.length <= 1500
 */
public class LongestRepeatingSubstring {

    public int longestRepeatingSubstring(String S) {
        if(S == null || S.length() == 0){
            return 0;
        }
        int n = S.length();
        int left = 0;
        int right = n;
        while(left <= right){
            int mid = left + (right - left) /2;
            if(search(mid, S, n) != -1){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;

    }

    private int search(int len, String S, int n){
        HashSet<Integer> visited = new HashSet<>();
        for(int start = 0; start < n - len + 1; start ++){
            String str = S.substring(start, start + len);
            int tmp = str.hashCode();
            if(visited.contains(tmp)){
                return start;
            }
            visited.add(tmp);
        }
        return -1;
    }
}
